// 中位数是有序序列最中间的那个数。
// 如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

// 给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。
// 窗口中有 k 个数，每次窗口向右移动 1 位。
// 你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

// 暴露接口
const medianSlidingWindow = function (nums: number[], k: number): number[] {
    let left = 0; // 左指针
    let right = k; // 右指针指向即将加入的右边界元素
    const res: number[] = []; // 结果数组
    const calMedianMethod = k % 2 === 0 ? calMedianEven : calMedianOdd; // 确认计算中位数的方式
    // 初始化窗口
    const slideWindow: number[] = [];
    for (let i = left; i < right; i++) {
        slideWindow.push(nums[i]);
    }
    // 首轮排序操作
    slideWindow.sort((a, b) => a - b);
    res.push(calMedianMethod(slideWindow));
    // 移动的过程中动态维护窗口引用
    while (right < nums.length) {
        // 找到左边界元素在窗口内的位置，并删除左边界元素
        const deleteIndex = slideWindow.indexOf(nums[left]);
        slideWindow.splice(deleteIndex, 1);
        // 二分搜索得到右边界元素在窗口内位置
        const insertIndex = binarySearch(slideWindow, nums[right]);
        slideWindow.splice(insertIndex, 0, nums[right]);
        res.push(calMedianMethod(slideWindow));
        right++;
        left++;
    }
    return res;
};

// 计算中位数---奇数情况
function calMedianOdd(sortedWindow: number[]): number {
    const len = sortedWindow.length;
    return sortedWindow[Math.floor(len / 2)];
}
// 计算中位数---偶数情况
function calMedianEven(sortedWindow: number[]): number {
    const len = sortedWindow.length;
    return (sortedWindow[Math.floor(len / 2)] +
        sortedWindow[Math.floor(len / 2) - 1]) / 2;
}

// 二分搜索
function binarySearch(sortedArr: number[], target: number): number {
    // 这里的搜索区间是左闭右开
    let left = 0;
    let right = sortedArr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (sortedArr[mid] > target) {
            right = mid;
        } else if (sortedArr[mid] <= target) {
            left = mid + 1;
        }
    }
    return right;
}


medianSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)


console.log(binarySearch([1, 3, 4, 5, 6], 10))
console.log(binarySearch([1, 3, 4, 5, 6], 0))